class Solution:
    def pacificAtlantic(self, matrix: list) -> list:
        if not matrix:
            return []
        self.matrix = matrix
        self.length, self.height = len(matrix[0]), len(matrix)
        if self.length < 2:
            return [[i, 0] for i in range(self.height)]
        elif self.height < 2:
            return [[0, j] for j in range(self.length)]
        self.taipingyang = [[0 for j in range(self.length)] for i in range(self.height)]
        self.daxiyang = [[0 for j in range(self.length)] for i in range(self.height)]
        self.check_taipingyang()
        self.check_daxiyang()
        res = []
        for i in range(self.height):
            for j in range(self.length):
                if self.taipingyang[i][j] and self.daxiyang[i][j]:
                    res.append([i, j])
        return res

    def check_taipingyang(self):
        self.taipingyang[0][0] = 1
        for j in range(1, self.length):
            self.taipingyang[0][j] = 1
            if not self.taipingyang[1][j] and self.matrix[1][j] >= self.matrix[0][j]:
                self.taipingyang[1][j] = 1
                self.check_round(1, j, self.taipingyang)
        for i in range(1, self.height):
            self.taipingyang[i][0] = 1
            if not self.taipingyang[i][1] and self.matrix[i][1] >= self.matrix[i][0]:
                self.taipingyang[i][1] = 1
                self.check_round(i, 1, self.taipingyang)

    def check_daxiyang(self):
        self.daxiyang[-1][-1] = 1
        for j in range(self.length - 1, -1, -1):
            self.daxiyang[-1][j] = 1
            if not self.daxiyang[-2][j] and self.matrix[-2][j] >= self.matrix[-1][j]:
                self.daxiyang[-2][j] = 1
                self.check_round(self.height - 2, j, self.daxiyang)
        for i in range(self.height - 1, -1, -1):
            self.daxiyang[i][-1] = 1
            if not self.daxiyang[i][-2] and self.matrix[i][-2] >= self.matrix[i][-1]:
                self.daxiyang[i][-2] = 1
                self.check_round(i, self.length - 2, self.daxiyang)

    def check_round(self, i, j, matrix):
        if i > 0 and not matrix[i - 1][j] and self.matrix[i - 1][j] >= self.matrix[i][j]:
            matrix[i - 1][j] = 1
            self.check_round(i - 1, j, matrix)
        if i < self.height - 1 and not matrix[i + 1][j] and self.matrix[i + 1][j] >= self.matrix[i][j]:
            matrix[i + 1][j] = 1
            self.check_round(i + 1, j, matrix)
        if j > 0 and not matrix[i][j - 1] and self.matrix[i][j - 1] >= self.matrix[i][j]:
            matrix[i][j - 1] = 1
            self.check_round(i, j - 1, matrix)
        if j < self.length - 1 and not matrix[i][j + 1] and self.matrix[i][j + 1] >= self.matrix[i][j]:
            matrix[i][j + 1] = 1
            self.check_round(i, j + 1, matrix)


a = Solution()
print(a.pacificAtlantic([[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]))
